/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	char buffer[PageFile::PAGE_SIZE];
	RC rc = pf.open(indexname, mode);	
	if (rc != 0)
		return RC_FILE_OPEN_FAILED;

	if (mode == 'r' || (mode == 'w' && pf.endPid() > 1))
	{
		pf.read(0, buffer);
		memcpy(&rootPid, buffer, sizeof(PageId));
		memcpy(&treeHeight, buffer+sizeof(PageId), sizeof(int));
	}

	
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	char buffer[PageFile::PAGE_SIZE];
	memcpy(buffer, &rootPid, sizeof(PageId));
	memcpy(buffer+sizeof(PageId), &treeHeight, sizeof(int));
	pf.write(0,buffer);
    return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	RC rc;
	IndexCursor cursor;	
	locate(key, cursor);	//cursor points to where to insert
	BTLeafNode ln;			//new leaf node
	ln.read(cursor.pid,pf);
	rc = ln.insert(key, rid);	//insert into leaf node

	if (rc == RC_NODE_FULL){	//insert and split leaf node
		BTLeafNode sibling;
		int siblingKey;

		ln.insertAndSplit(key, rid, sibling, siblingKey);
		PageId epid = pf.endPid();	
		sibling.write(epid, pf);	//write new leaf node to page epid

		BTNonLeafNode nl;
		BTNonLeafNode sibNL;
		int sibNLkey = siblingKey;
		int index = 1;
		int midKey;
		PageId pid;
		while(rc == RC_NODE_FULL && index < treeHeight){
			pid = parentList[treeHeight-1-index];
			nl.read(pid,pf);
			rc = nl.insert(siblingKey, epid);
			if (rc == RC_NODE_FULL){
				nl.insertAndSplit(sibNLkey, pid, sibNL, midKey);
				sibNLkey = midKey;
				sibNL.write(pf.endPid(), pf);
				nl.write(pid, pf);
				index++;
			}
			else{
				nl.write(pid, pf);
				break;
			}
		}
		if (treeHeight == index){
			BTNonLeafNode root;
			root.initializeRoot(pid,sibNLkey,pf.endPid()-1);
			rootPid = pf.endPid()-1;
			treeHeight++;
		}

		ln.write(cursor.pid, pf);

	}

    return 0;
}


/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+ tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	int * plist = new int[treeHeight];
	if (treeHeight <= 0)
		return RC_NO_SUCH_RECORD;
	if (treeHeight == 1){
		int eid;
		BTLeafNode lf;
		lf.read(rootPid, pf);
		lf.locate(searchKey, eid);
		cursor.pid = rootPid;
		cursor.eid = eid;
		plist[0] = rootPid;
	}
	if (treeHeight > 1){
		int sDepth = 1;
		int tpid = rootPid;
		while(sDepth < treeHeight){
			BTNonLeafNode nl;
			nl.read(tpid, pf);
			nl.locateChildPtr(searchKey, tpid);
			plist[sDepth-1] = tpid;
			sDepth++;
		}
		if (sDepth == treeHeight){
			int eid;
			BTLeafNode lf;
			lf.read(tpid, pf);
			lf.locate(searchKey, eid);
			cursor.pid = rootPid;
			cursor.eid = eid;
			plist[sDepth-1] = tpid;
		}
	}
    return 0;
	parentList = plist;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode ln;
	ln.read(cursor.pid, pf);
	ln.readEntry(cursor.eid, key, rid);
	int keyCount = ln.getKeyCount();
	if (cursor.pid >= pf.endPid())
		return RC_INVALID_CURSOR;
	if (cursor.eid > keyCount)
		return RC_INVALID_CURSOR;

	if (cursor.eid == keyCount){
		cursor.pid = ln.getNextNodePtr();
		cursor.eid = 0;
	}
	else{
	cursor.eid++;
	}
    return 0;
}
